package com.my.leetcode;

import java.util.Arrays;
import java.util.Stack;

public class SortProblems {


    public static void main(String[] args) {

        SortProblems sortProblems = new SortProblems();

        int [] A= {6,1,7,5,9,5,3,2};
        //sortProblems.sortedSquares(A);
        sortProblems.bubbleSort(A);
        System.out.println("========" + Arrays.toString(A));
    }


    /**
     * @author zlx
     * @Description 84. 柱状图中最大的矩形
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
     * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
     *
     * 示例:
     *
     * 输入: [2,1,5,6,2,3]
     * 输出: 10
     *
     * 解法一： 暴力破解法，求最大面积
     * 解法二：双指针法，对height[i] 向左找到第一个比height[i]小的left，向右找到第一个比height[i]小的right,
     * 以i为中心的最大柱状面积：max[height[i]] = height[i] * (right - right - 1)
     * 解法三：基于单调递增栈进行求解
     * @Date 3/27/21
     * @Param [heights]
     * @return int
     **/
    public int largestRectangleArea(int[] heights) {

        if(heights == null || heights.length == 0){
            return 0;
        }

        int res = 0;
        for(int i = 0;i < heights.length;i++){

            int area = heights[i];
            int minHeight = heights[i];
            for(int j = i-1;j>=0;j--){

                minHeight = Math.min(minHeight, heights[j]);
                area = Math.max(area, minHeight * (i - j + 1));
            }
            res = Math.max(area, res);
        }
        return res;
    }

    public int largestRectangleAreaII(int[] heights) {

        if(heights == null || heights.length == 0){
            return 0;
        }
        int res = 0;
        for(int i = 0;i < heights.length;i++){

            int left = i, right = i;
            while (left >= 0 && heights[left] >= heights[i]){
                left --;
            }

            while (right < heights.length && heights[right] >= heights[i]){
                right ++;
            }
            res = Math.max(res, heights[i] * (right - left -1));
        }
        return res;
    }

    public int largestRectangleAreaIII(int[] heights) {

        if(heights == null || heights.length == 0){
            return 0;
        }
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);

        Stack<Integer> mono_stack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }


    /**
     * @author zlx
     * @Description 85. 最大矩形 hard
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     *
     *
     *
     * 示例 1：
     *
     *
     * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
     * 输出：6
     * 解释：最大矩形如上图所示。
     * 示例 2：
     *
     * 输入：matrix = []
     * 输出：0
     * 示例 3：
     *
     * 输入：matrix = [["0"]]
     * 输出：0
     * 示例 4：
     *
     * 输入：matrix = [["1"]]
     * 输出：1
     * 示例 5：
     *
     * 输入：matrix = [["0","0"]]
     * 输出：0
     *
     *
     * 提示：
     *
     * rows == matrix.length
     * cols == matrix[0].length
     * 0 <= row, cols <= 200
     * matrix[i][j] 为 '0' 或 '1'
     * @Date 3/27/21
     * @Param [matrix]
     * @return int
     **/
    public int maximalRectangle(char[][] matrix) {

        if(matrix == null || matrix.length == 0){
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;

        int matrixVal [][] = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){

                if(matrix[i][j] == '1'){
                    if(j == 0){
                        matrixVal[i][j] = 1;
                    }
                    else  {
                        matrixVal[i][j] = matrixVal[i][j - 1] + 1;
                    }
                }
            }
        }

        int res = 0;
        for(int i = 0;i < m;i++){

            for(int j = 0;j < n;j++){

                if(matrix[i][j] == '0'){
                    continue;
                }

                int width = matrixVal[i][j];
                int area = width;
                for(int k = i -1;k >=0;k--){
                    width = Math.min(width, matrixVal[k][j]);
                    area = Math.max(area, width * (i - k + 1));
                }
                res = Math.max(res, area);
            }
        }
        return res;
    }



    /**
     * @author zlx
     * @Description 1727. 重新排列后的最大子矩阵
     * 给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。
     *
     * 请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
     * 输出：4
     * 解释：你可以按照上图方式重新排列矩阵的每一列。
     * 最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。
     * 示例 2：
     *
     *
     *
     * 输入：matrix = [[1,0,1,0,1]]
     * 输出：3
     * 解释：你可以按照上图方式重新排列矩阵的每一列。
     * 最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。
     * 示例 3：
     *
     * 输入：matrix = [[1,1,0],[1,0,1]]
     * 输出：2
     * 解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。
     * 示例 4：
     *
     * 输入：matrix = [[0,0],[0,0]]
     * 输出：0
     * 解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。
     *
     *
     * 提示：
     *
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m * n <= 105
     * matrix[i][j] 要么是 0 ，要么是 1 。
     * @Date 3/27/21
     * @Param [matrix]
     * @return int
     **/
    public int largestSubmatrix(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;

        //计算matrix[i][j] = 1 时， 第j列，0到i行的1个数
        for(int i = 1;i < m;i++){
            for(int j = 0;j < n;j++){

                if(matrix[i][j] == 1){
                    matrix[i][j] += matrix[i-1][j];
                }
            }
        }

        int res = 0;
        for(int i = 0;i < m;i++){

            Arrays.sort(matrix[i]);
            for(int j = n - 1;j >= 0;j--){

                int height = matrix[i][j];
                res = Math.max(res, height * (m - j));
            }
        }

        return res;
    }

    public int[] sortedSquares(int[] A) {

        if(A == null || A.length <= 0){
            return A;
        }

        for(int i = 0;i < A.length;i++){

            A[i] = Math.abs(A[i]);
        }
        quickSort(A, 0, A.length - 1);
        System.out.println(Arrays.toString(A));
        int [] res = new int [A.length];
        for(int i = 0;i < res.length;i++){
            res[i] = A[i] * A[i];
        }
        return res;
    }


    //冒泡排序
    public void bubbleSort(int [] A){

        for(int i = 0;i < A.length - 1;i++){
            for(int j = 0;j < A.length - 1 - i;j++){
                if(A[j] > A[j+1]){
                    int tmp = A[j];
                    A[j] = A[j + 1];
                    A[j+1] = tmp;
                }
            }
        }
    }

    //快排
    public void quickSort(int [] A, int start, int end){

        if(start >= end){
            return ;
        }
        int flagVal = A[start];
        int left = start;
        int right = end;
        while (left != right) {
            while (left < right) {
                if (A[right] >= flagVal) {
                    right--;
                } else {
                    A[left] = A[right];
                    break;
                }
            }

            while (left < right) {
                if (A[left] <= flagVal) {
                    left++;
                } else {
                    A[right] = A[left];
                    break;
                }
            }
        }
        A[left] = flagVal;
        quickSort(A, start, left - 1);
        quickSort(A, left + 1, end);
    }


}
